package leetcode.primary;

public class T208 {

    TreeNode1 root;
    /** Initialize your data structure here. */
    public T208() {
        root = new TreeNode1();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        if (word==null || word.length()==0){
            return;
        }
        TreeNode1 node = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i)-'a';
            if (node.next[index]==null){
                node.next[index] = new TreeNode1();
            }
            node = node.next[index];
        }
        node.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TreeNode1 node = sort(word);
        return node != null && node.isEnd;

    }

    private TreeNode1 sort(String str){
        TreeNode1 node = root;
        for (int i = 0; i < str.length(); i++) {
            int index =str.charAt(i)-'a';
            if (node==null || node.next[index]==null){
                return null;
            }
            node = node.next[index];
        }
        return node;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TreeNode1 node = sort(prefix);
        return node != null;
    }

    public static void main(String[] args) {
        T208 t208 = new T208();
        t208.insert("apple");
        System.out.println(t208.search("apple"));

        System.out.println(t208.search("app"));
        System.out.println(t208.startsWith("app"));

        t208.insert("app");
        System.out.println(t208.search("app"));
    }
}

class TreeNode1 {
    boolean isEnd;
    TreeNode1[] next;

    public TreeNode1() {
        isEnd = false;
        next = new TreeNode1[26];
    }

    public TreeNode1(boolean isEnd, TreeNode1[] next) {
        this.isEnd = isEnd;
        this.next = next;
    }
}
